package com.berchen.算法;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

/**
 * 选择排序
 *
 * 第一轮：从所有数据中找到一个最小的 数据 和第一个数据进行交换
 * 第二轮 从第一个数据之后的所有数据中找到一个最小的  和第二个数据进行交换
 * 第三轮 从第二个数据自后的所有数据中找到一个最小的 和第三个数据进行交换
 * 。。。
 * 执行 n-1 轮之后  数据就有序了
 *
 */
public class SelectSort {

    public static void main(String[] args) {

        int [] arr={-1,0,21,3};
        int [] testArr=new int[80000];
        for(int i =0;i<testArr.length;i++){
            testArr[i]=(int)(Math.random()*80000);
        }
        Instant start=Instant.now();
        selectSort(testArr);
        Instant end=Instant.now();
        System.out.println(Duration.between(start,end).toMillis()); // 2326 毫秒
//        System.out.println(Arrays.toString(testArr));
    }

    /**
     * 选择排序
     * @param arr
     */
    public static void selectSort(int[] arr){

        for(int i=0;i<arr.length-1;i++){
            int min=arr[i];
            int minIndex=i;
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]<min){
                    min=arr[j];
                    minIndex=j;
                }
            }
            if(minIndex!=i){
                arr[minIndex]=arr[i];
                arr[i]=min;
            }
        }
    }
}
